package com.hc.programming.string;

/**
 * 32.给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * <p>
 * 示例 1：
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * <p>
 * 示例 2：
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * <p>
 * 示例 3：
 * 输入：s = ""
 * 输出：0
 * <p>
 * 提示：
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/6/12 9:46
 */
public class 最长有效括号 {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("()((())()"));
    }

    public static int longestValidParentheses(String s) {
        int[] lens = new int[s.length()];
        int res = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                int left = i - lens[i-1] - 1;
                if (left >= 0 && s.charAt(left) == '(') {
                    lens[i] = lens[i - 1] + 2 + (left > 0 ? lens[left - 1] : 0);
                }
//                if (s.charAt(i - 1) == '(') {
//                    lens[i] = 2 + (i > 2 ? lens[i - 2] : 0);
//                } else if (i > lens[i - 1] && s.charAt(i - lens[i - 1] - 1) == '(') {
//                    lens[i] = lens[i - 1] + 2 + (i > lens[i - 1] + 2 ? lens[i - lens[i - 1] - 2] : 0);
//                }
                res = Math.max(res, lens[i]);
            }
        }
        return res;
    }

}
